package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-18 13:51
 **/
public class LeetCode75 {


    //双指针(一次遍历)
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p1 = 0;
        int p2 = n - 1;
        for (int i = 0; i <= p2; i++) {
            while (p2 >= 0 && nums[p2] == 2) {
                --p2;
            }
            //这里循环是因为可能把2换到末尾,而末尾刚好也是2,所以需要继续
            if (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }

            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            }
        }
    }

    //单指针(两次遍历)
    /*public void sortColors(int[] nums) {
        int ptr = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                int temp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = temp;
                ++ptr;
            }
        }

        for (int i = ptr; i < n; i++) {
            if (nums[i] == 1) {
                int temp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = temp;
                ++ptr;
            }
        }
    }*/

    //api调用
    /*public void sortColors(int[] nums) {
        Arrays.sort(nums);
    }*/

}
